package com.demo77_组合;

import java.util.ArrayList;
import java.util.List;

/**
 * 注意点:  组合是没有顺序的,  只能 [1,2]  和 [2,1]  是同一个组合
 * <p>
 * 排列是有顺序的  要注意到!!!!!
 */
public class Solution_剪枝 {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        List<List<Integer>> combine = combine(100, 4);
        System.out.println(combine);
        long end = System.currentTimeMillis();
        System.out.println(end - start);

    }

    public static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> arrayLists = new ArrayList<>();
        ArrayList<Integer> path = new ArrayList<>();

        dfs(n, k, 1, arrayLists, path);

        return arrayLists;
    }

    private static void dfs(int n, int k, int startIndex, List<List<Integer>> arrayLists, ArrayList<Integer> path) {
        // 边界条件
        if (path.size() == k) {
            // 收集结果:  这个集合添加进数组有一点问题, 这个方法太笨了
            ArrayList<Integer> copy = new ArrayList<>();
            for (int i = 0; i < k; i++) {
                copy.add(path.get(i));
            }

            // 这里也可以用浅克隆来实现  序列化和反序列化
            arrayLists.add(copy);
            return;
        }
        // 集合中的剩余元素的个数  【剪枝】
        /*int remain = n-startIndex+1;
        if (remain+path.size()<k){
            return;
        }*/


        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {

            path.add(i);
            dfs(n, k, i + 1, arrayLists, path);

            // 上一层遍历结束, 或者是失败.  回溯, 把元素最后面的元素弹出---删除也可以  【回溯】
            path.remove(path.size() - 1);

        }
    }


}
